package william.array;

/**
 * @author ZhangShenao
 * @date 2024/4/26
 * @description <a href="https://leetcode.cn/problems/next-permutation/solutions/479151/xia-yi-ge-pai-lie-by-leetcode-solution/">...</a>
 */
public class Leetcode31_下一个排列 {
    /**
     * Step1: 从后往前遍历数组,找到较小数nums[i],使得nums[i]<nums[i+1]
     * Step2: 从后往前遍历数组,在[i+1,N-1]区间内,找到较大数nums[j],使得nums[j]>nums[i]
     * Step3: 交换i,j位置的元素
     * Step4: 将数组nums的[i+1,N-1]区间进行反转,转换成升序
     * <p>
     * 时间复杂度O(N) 遍历两次数组
     * 空间复杂度O(1)
     */
    public void nextPermutation(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 2) {
            return;
        }

        //从后往前遍历数组,找到较小数nums[i],使得nums[i]<nums[i+1]
        int N = nums.length;
        int i = N - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        //如果未找到较小数nums[i],说明当前的排列已经是全降序排列,则直接反转即可
        if (i < 0) {
            reverse(nums, 0);
            return;
        }

        //从后往前遍历数组,在[i+1,N-1]区间内,找到较大数nums[j],使得nums[j]>nums[i]
        int j = N - 1;
        while (j >= 0 && nums[j] <= nums[i]) {
            j--;
        }

        //交换i,j位置的元素
        swap(nums, i, j);

        //将数组nums的[i+1,N-1]区间进行反转,转换成升序
        reverse(nums, i + 1);
    }

    /**
     * 将数组nums的[start,N-1]区间进行反转
     */
    private void reverse(int[] nums, int start) {
        int l = start;
        int r = nums.length - 1;
        while (l < r) {
            swap(nums, l++, r--);
        }
    }

    /**
     * 交换数组nums中i,j两个位置的元素
     */
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
